package com.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 692. 前K个高频单词
 *
 * @author yml
 *
 */
public class LeetCode692 {

	public static void main(String[] arg0) {
		String[] words = new String[] { "a", "aa", "aaa" };
		int k = 3;
		System.out.println("前" + k + "个高频单词  = "
				+ Arrays.toString(topKFrequent(words, k).toArray()));
	}

	public static List<String> topKFrequent(String[] words, int k) {
		Arrays.sort(words);
		System.out.println("排序后的words数组 = " + Arrays.toString(words));
		List<String> results = new LinkedList<>();

		LinkedList<Integer> counts = new LinkedList<>();
		String beforeStr = "";
		int count = 0;
		for (int i = 0; i < words.length; i++) {
			if (beforeStr.equals(words[i])) {
				count++;
			}

			if (!beforeStr.equals(words[i]) || i == words.length - 1) {
				if (count != 0) {
					if (counts.size() == 0) {
						counts.add(count);
						results.add(beforeStr);
					} else if (counts.size() < k) {
						// 因为集合还未添加到k个，所以考虑继续往最后填充的情况
						if (count <= counts.get(counts.size() - 1)) {
							counts.add(count);
							results.add(beforeStr);
						} else {
							midSort(count, beforeStr, 0, counts.size(), counts,
									results, k);
						}
					} else {
						if (count > counts.get(k - 1)) {
							midSort(count, beforeStr, 0, k, counts, results, k);
						}
					}
				}

				if (i == words.length - 1 && count == 1) { // 多执行一次，当最后一个字符串只有一次没重复的时候
					beforeStr = words[i];
					if (counts.size() == 0) {
						counts.add(count);
						results.add(beforeStr);
					} else if (counts.size() < k) {
						// 因为集合还未添加到k个，所以考虑继续往最后填充的情况
						if (count <= counts.get(counts.size() - 1)) {
							counts.add(count);
							results.add(beforeStr);
						} else {
							midSort(count, beforeStr, 0, counts.size(), counts,
									results, k);
						}
					} else {
						if (count > counts.get(k - 1)) {
							midSort(count, beforeStr, 0, k, counts, results, k);
						}
					}
				}

				count = 1;
				beforeStr = words[i];
			}
		}

		return results;
	}

	public static void midSort(int count, String beforeStr, int startIndex,
							   int endIndex, LinkedList<Integer> counts, List<String> results,
							   int k) {
		if (endIndex - startIndex < 256) {
			for (int j = startIndex; j < endIndex; j++) {
				if (count > counts.get(j)) {
					counts.add(j, count);
					results.add(j, beforeStr);
					if (results.size() > k) {
						results.remove(results.size() - 1);
					}
					break;
				}
			}
		} else {
			int midIndex = (startIndex + endIndex) / 2;
			if (count > counts.get(midIndex)) {
				midSort(count, beforeStr, startIndex, midIndex, counts,
						results, k);
			} else {
				midSort(count, beforeStr, midIndex + 1, endIndex, counts,
						results, k);
			}
		}
	}

}
